Thời Hán Ai đế, Thuật nhờ cha là Công Tôn Nhân mà được làm Lang; sau đó Nhân làm Hà Nam đô úy, nên Thuật được bổ làm Thanh Thủy (huyện) trưởng. Vì ông còn nhỏ tuổi, nên Nhân sai Môn hạ duyện (các viên chức cấp phó) của mình đi theo. Hơn tháng, bọn họ xin về, nói với mọi người rằng: "Thuật chẳng cần dạy dỗ nữa!" Về sau thái thú thấy ông có năng lực, sai kiêm cả năm huyện. Thuật sửa sang chính sự, trộm cướp không còn, người trong quận cho là có quỷ thần. Sau khi Vương Mãng soán ngôi, ông làm Đạo Giang tốt chánh (tương đương thái thú), ở Lâm Cung, lại được tiếng là có năng lực.

Khi Canh Thủy đế lên ngôi (23), các nơi khởi binh hưởng ứng, Thuật sai sứ nghênh đón người Nam Dương là Hổ nha tướng quân (tự xưng) Tông Thành ở Hán Trung. Thành đến Thành Đô, thả cho bộ hạ cướp bóc ngang ngược, ông có ý ghét, kêu gọi hào kiệt trong huyện khởi binh, trước là dẹp Thành, sau là giúp Hán, được mọi người ủng hộ. Thuật sai người trá làm sứ giả nhà Hán từ phương đông đến, cho ông làm Phụ Hán tướng quân, ban ấn thụ Thục Quận thái thú kiêm Ích Châu mục. Thuật tuyển hơn ngàn tinh binh, tây tiến tấn công Thành. Họ đến Thành Đô, lực lượng lên đến vài ngàn, bèn đánh thành, phá được. Tướng của Thành là Viên Phó giết Thành, đưa quân về hàng.